package offerbook;

import utils.TreeNode;
import utils.TreeUtil;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @date 2019/11/10 0010 下午 9:25
 * 请实现一个函数，用来判断一颗二叉树是不是对称的。
 * 注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
 *
 *
 * 方式1：把当前二叉树给镜像了，然后遍历两颗二叉树。
 * 难点：怎么克隆二叉树
 * 镜像二叉树见{@link Code19_MirrorBT}
 *
 * 方式2：
 * 二叉树的前序遍历：前左右
 * 二叉树的反前序遍历：前右左，
 * 这两次遍历如果一致，则是对称二叉树。
 *
 * 中序遍历：左中右，--> 与 左右中遍历对比
 * 后续遍历：也一样。
 *
 * 3种遍历都可以改，那么总共就是6种方法。
 *
 * 以上做法存在一个问题。就是当二叉树不对称，但是所有节点的值都一样，那么以上方法不对。
 * 主要是没有考虑空节点。  可以把空节点加入栈，用一个特殊的值表示。
 *
 *
 * 对以上方法优化：在同义一次遍历中，去做。
 *
 *
 *
 */
public class Code59_MirrorBT_SimilarBT {


    /*
     * 存在的问题：当一棵树的所有节点都是同一个值，没有考虑到null的问题。见笔记分析。
     * 解决：当node == null，也要入队一个数，作为标记。
     */
    public static boolean isSymmetrical1(TreeNode pRoot) {
        if(pRoot == null){
            return true;
        }
        Queue<Integer> queue = new LinkedList<>();
        preTraverse(pRoot,queue);
        return preTraverseOpposite(pRoot,queue);
    }
    private static void preTraverse(TreeNode pRoot, Queue<Integer> queue) {

        if(pRoot == null){
            queue.offer(Integer.MIN_VALUE);
            return;
        }

        queue.offer(pRoot.val);

        preTraverse(pRoot.left,queue);

        preTraverse(pRoot.right,queue);
    }
    private static boolean preTraverseOpposite(TreeNode pRoot, Queue<Integer> queue) {
        if(pRoot== null){
            return queue.poll() == Integer.MIN_VALUE;
        }
        //出队
        if(queue.poll() != pRoot.val){
            return false;
        }
        return preTraverseOpposite(pRoot.right,queue)&& preTraverseOpposite(pRoot.left,queue);
    }

    /**
     * 方式2：在一次遍历中处理。通过测试
     */
    public static boolean isSymmetrical2(TreeNode pRoot) {
        if(pRoot == null){
            return false;
        }

        return preOrder(pRoot,pRoot);
    }

    private static boolean preOrder(TreeNode pRoot1, TreeNode pRoot2) {
        // base case
        if(pRoot1 == null || pRoot2 == null){
            return pRoot1 == pRoot2; // 都是null则true，只有一个null为false
        }

        //先序遍历，在这里处理
        if(pRoot1.val != pRoot2.val){
            return false;
        }
        return preOrder(pRoot1.left,pRoot2.right) && preOrder(pRoot1.right,pRoot2.left);
    }


    /**
     * 方式3：层次遍历。一个从左到右层次遍历，一个从右到左。准备两个栈。
     * @param root
     * @return
     */
    private boolean iterator1(TreeNode root) {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> queue1 = new LinkedList<>();
        queue.offer(root);
        queue1.offer(root);
        while (!queue.isEmpty()) {
            TreeNode root1 = queue.poll();
            TreeNode root2 = queue1.poll();
            //这里很重要，是basecase
            if (root1 == null && root2 == null) continue;
            if (root1 == null || root2 == null) return false;
            //root1代表左侧分支，root2代表右侧分支。对应的左右孩子都要一致。
            if (root1.val != root2.val) return false;
            //第1个从左到右层次遍历，空也要入队
            queue.offer(root1.left);
            queue.offer(root1.right);

            //第2个从右到左层次遍历，空也要入队
            queue.offer(root2.right);
            queue.offer(root2.left);
        }
        return true;
    }
    /**
     * 方式4：对层次遍历空间优化，使用1个队列。
     * <p>
     * 每次入队两个点。第一个是从左到右层次遍历，第二个是从右到左层次遍历。
     * <p>
     * 或者用两个队列也行。
     * <p>
     */
    private boolean iterator2(TreeNode root) {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode root1 = queue.poll();
            TreeNode root2 = queue.poll();
            if (root1 == null && root2 == null) continue;
            if (root1 == null || root2 == null) return false;
            //root1代表左侧分支，root2代表右侧分支。对应的左右孩子都要一致。
            if (root1.val != root2.val) return false;
            //第1个从左到右层次遍历
            //第2个从右到左层次遍历
            queue.offer(root1.left);
            queue.offer(root2.right);

            queue.offer(root1.right);
            queue.offer(root2.left);
        }
        return true;
    }

    public static void main(String[] args) {

        /*TreeNode root1 = new TreeNode(8);
        root1.left = new TreeNode(6);
        root1.right = new TreeNode(10);
        root1.left.left = new TreeNode(5);
        root1.left.right = new TreeNode(7);
        root1.right.left = new TreeNode(9);
        root1.right.right = new TreeNode(11);
        PrintBinaryTree.printTree(root1);*/
        TreeNode root1 = new TreeNode(5);
        root1.left = new TreeNode(3);

        root1.left.left = new TreeNode(4);
        root1.left.left.left = new TreeNode(2);
        root1.left.left.left.left = new TreeNode(1);

        root1.right = new TreeNode(3);
        root1.right.right = new TreeNode(4);
        root1.right.right.right = new TreeNode(6);
        root1.right.right.right.right = new TreeNode(1);

        TreeUtil.printTree(root1);
        System.out.println(isSymmetrical1(root1));

    }
}
